模拟赛题解/2025.10.22 模拟赛

T1-动态构图（dynamic）

题面

阿狸有一个包含 $n$ 个节点，初始有 $m$ 条边的无向联通图 $G$。由于他的朋友都去度假了，没人跟他研究图论算法，所以他决定自己用这个无向图做一个游戏。

游戏分为多个回合。每一回合，阿狸会新建一个与无向图 $G$ 完全相同的副本 $G'$，然后枚举三个不同的节点 $x, y, z$，如果 $(x, y), (y, z)$ 均在 $G$ 上存在边，而 $(x, z)$ 在 $G$ 上没有连边，则阿狸会在 $G'$ 上建立 $(x, z)$ 这条边。在所有可以添加的边均加入 $G'$ 后，阿狸会让 $G \leftarrow G'$，并结束该回合。

在某个回合结束后，若对于任意两个不同的节点 $x, y$，都满足 $(x, y)$ 这条边在 $G$ 中存在，则游戏立即结束，阿狸的最终得分为游戏经过的回合数量。如果初始的 $G$ 已经满足了该条件，则回合数是 0。

$1\leq n,m\leq10^5$。

题解

先考虑一条链上会发生什么，简单模拟发现内容近似于每个点向旁边的另一个点合并，显然轮次是 $\log len$（$len$ 是序列长度）。

在图上，轮次取决于最长的一条链，于是问题转化成求最长链长度的 $\log$。

注意到，从任何一个点出发，一定存在一个点满足两点之间的距离超过最长链长度的一半。

• 证明：假设有一个点 $i$ 不满足该性质，则剩余点两两之间的距离都不会超过它们分别与 $i$ 的距离和，于是发现最长链长度小于最长链长度，矛盾。

所以只需要选择一个点，从该点出发找到距离最远的点，其距离的 $\log$ 一定是最长链的 $\log$ 或少 $1$。

由于可以给出两个点，只要其中之一正确即可，因此可以直接输出 $\log(\max_{i=1}^n dis(1,i))$ 和其 $+1$。

T2-重力排序（epotential）

题面

阿狸找到了无限多的、五颜六色的沙块，于是他决定用这些沙块建一个三角形建筑。在此过程中，他注意到沙块是不能悬空，于是他发现了一种新的排序算法：重力排序。

阿狸先选择了一个 $1 \sim n$ 的排列 $p$，以及长度为 $n$ 的颜色序列 $c$。在选择 $p, c$ 之后，他决定实行重力排序算法。

具体而言，重力排序算法是这样实现的：对于所有满足 $1 \leq i \leq n$ 的 $i$，在所有 $1 \leq j \leq p_i$ 的位置 $(i, j)$ 上放置一个颜色为 $c_i$ 的沙块。随后，施加向下的重力，使所有沙块尽可能下落。

这里，位置 $(x, y)$ 表示从上往下第 $x$ 行、从左往右第 $y$ 列的格子。

在算法实现后，阿狸给重力排序后的结果拍了照片。

不过阿狸是一个好奇心很强的人。阿狸希望你来计算，有多少个不同的排列 $p'$（注意 $p'$ 可以是 $p$ 本身），使得在用 $p', c$ 来完成重力排序算法之后，每个位置上的沙块颜色与照片中的相同。

两个排列 $p_1, p_2$ 不同，当且仅当存在正整数 $i \in [1, n]$，满足 $p_1^i \neq p_2^i$。

阿狸没时间记忆过大的数字，所以你的答案要对 998244353 取模。

$1\leq p_i\leq n\leq2\times10^5,1\leq T\leq10,1\leq c_i\leq2\times10^5$。

题解

观察样例，不难发现对于同色的第 $i,j$ 两行，如果它们的 $p_i$ 可以相互交换，那么对于任意正整数 $x \in (i,j)$，有 $p_x < \min(p_i, p_j)$。

很多人可能会想到，直接连边然后算连通块大小的阶乘乘积，但这是错误的，比如 $p = \{2,1,4,3,5\}, c = \{1,2,1,2,1\}$ 时，$p' = \{5,1,4,3,2\}$ 不是一个合法解。

考虑枚举 $i = 1,2,\ldots,n$，找到 $p_x = i$ 的这个位置 $x$，然后计算 $x$ 这一行能出现在 $p'$ 的哪些位置。在不管 $p$ 对应值 $<i$ 的那些行的情况下，$x$ 可以交换到的位置一定是一个连续的段，也就是 $x$ 所在的极长连续段。链表和并查集维护即可。

T3-魔法对轰（apollyon）

题面

阿狸有一块长 $n$ 米，宽 1 米的白板。他将这块白板划分为一排的 $n$ 个格子，每个格子的长宽均为 1 米。他让这些格子从左到右依次编号为 $1 \sim n$。

阿狸有 $m$ 种魔法，第 $i$ 种魔法可以让编号 $[l_i, r_i]$ 范围内的格子染上颜色 $c_i$。如果某个格子被多次染色，以最后一次的颜色为准。

阿狸需要使用每种魔法恰好一次，但可以决定每种魔法的施展顺序。请帮他决定一个顺序，使得最终对于每个正整数 $i \in [1, n]$，第 $i$ 个格子最终的颜色与 $b_i$ 相同。

$1\leq n,m\leq5\times10^5,1\leq c_i\leq5\times10^5,0\leq b_i\leq5\times10^5$。

题解

注意到每个位置对应的权值只与覆盖这一位置的最后一次操作有关，所以考虑倒序选择操作。

问题变为，如果某个位置被操作一次，则颜色被永久保留，求一组方案。那么，在一个位置被涂色后，可以任意对其做其余操作。

考虑贪心策略。每次选一个当前可以选择区间，标记这个区间内的所有位置。如果对于某个区间包含的每个位置，要么被标记，要么其颜色与操作对应相同，则这个区间就是可以选择的。

容易得出，这样选择一定不劣，复杂度为 $\Theta(nm)$。

上述做法显然不能通过，需要优化。这里用到了一个 trick。

使用线段树，将每个操作区间拆成 $\log n$ 级别个线段树上的不交子区间，如果这些区间是可以被选择的，那么整个原来的区间也是可以被选择的。

维护每个位置对应的需要涂的颜色，记录线段树每个节点的 $val$：

• 如果这个线段树节点对应区间中，每个位置均被标记，即整个区间剩下的涂色方案可以任意，则 $val$ 为 0。
• 如果这个区间中，除了被标记的位置，其余位置需要涂的颜色都为 $c$，则 $val$ 为 $c$。
• 否则，需要涂的颜色至少有两种，$val$ 为 $-1$。

第一种情况下，这个线段树节点对应的所有操作都是可选的；第二种情况下，颜色为 $val$ 的操作可选；第三种情况下都不能选。

涂色操作是好维护的，直接暴力修改颜色就行，如果遇到 $val$ 是 0 的节点就不用往下搜了。

用一个队列维护一下类似拓扑的过程即可。

注意 $b_i$ 存在 0，这种情况特判一下，显然所有操作不能覆盖这些位置中的任意一个。

T4-魔法对轰（apollyon）

题面

阿狸有 $n$ 块符文，他将符文排成一排，并按照从左至右的顺序依次标号为 $1 \sim n$。每块符文都有对应的魔法值，第 $i$ 块符文的魔法值为 $a_i$。

由于虚空法术的侵入，有 $k$ 块符文的位置已经无法改变了，这些符文的标号分别为 $x_1, x_2, \ldots, x_k$。

阿狸可以对除了标号为 $x_1, x_2, \ldots, x_k$ 的其余所有符文进行重新排序，使得在排序之后，对于每个 $i = 1, 2, \ldots, k$，从左至右第 $x_i$ 个符文的标号仍然为 $x_i$。

阿狸希望用这 $n$ 块符文组成一个魔法阵。具体地，假设在重新排列后，从左到右第 $i$ 块符文的魔法值为 $b_i$，则魔法阵的法力消耗值为

$$\sum_{i=1}^{n-1} \max(b_i, b_{i+1})$$

阿狸希望在重新排列后，魔法阵的法力消耗值尽可能地小，以更好地与虚空法术对抗。输出这个最小可能的法力消耗值。

$1\leq n\leq300,0\leq k\leq\min(n,6),1\leq a_i\leq10^6,1\leq x_1\leq x_2\leq\dots\leq x_k\leq n$。

题解

首先有 $\max(x,y) = \frac{x+y+1}{2}$，所以题目相当于求 $\sum_{i=1}^{n-1} |a_i - a_{i+1}|$ 的最小值。

考虑 $K = 0$ 的做法，显然是把 $a_i$ 从小到大排序然后算答案。

如果 $K > 0$，那么相当于把原序列分成 $K + 1$ 段（这里对段的定义是：没有被卡住的瓷砖组成的极长连续段），然后在段内填数。同样，对于每段的内部，从小到大、或者从大到小排序一定是最优的。

为了方便，把 $a$ 中所有没被卡住的瓷砖的丑陋值拉出来，排序，存在 $b$ 数组中。

而对于一个单调不增、或单调不降的数列 $a$，有 $\sum_{i=1}^{|a|-1} |a_i - a_{i+1}| = |a_1 - a_{|a|}|$。所以对于某一段，假设这一段前面一个被卡住的瓷砖的丑陋值为 $L$，这一段后面的那个为 $R$，段内首个瓷砖的丑陋值为 $b_l$，最后一个为 $b_r$，则这一段对答案的贡献为 $|L - b_l| + (b_r - b_l) + |b_r - R|$。

可以看到，某一段对答案的贡献只与 $b_l, b_r, L, R$ 有关。而 $L, R$ 是固定的，所以我们接下来的算法中只需决策选择哪些数列 $(l, r)$。

以下归并所有 $L > R$ 的情况，并转化为 $L < R$，相当于把段进行一次翻转，这样操作不影响其他段。

可以证明，选择的这些数列 $(l, r)$ 对应的线段 $[l, r]$ 要么无交，要么为包含关系。

考虑反证法：在 $L \leq R$ 的时候，段内的元素一定是单调不降的。那么，当 $b_l$ 变大时，或者 $b_r$ 变小时，$|L - b_l| + (b_r - b_l) + |b_r - R|$ 的值不会变大。如果存在选择的两个数列 $(l, r), (l', r')$ 满足 $l \leq l' \leq r \leq r'$，则交换 $l', r$ 一定不劣。

考虑怎么实现这个选择数对的过程。注意到 $n, k$ 的范围都不是很大，区间 $dp$ 似乎是可行的方向。为了方便，以下记录 $len_S$ 表示 $S$ 集合内所有段的长度总和。

设 $dp_{l,r,S}$ 表示在 $[l, r]$ 区间内选择集合 $S$ 内对应的所有段所需的最小代价。有转移方程如下：

$$\begin{aligned} dp_{l,r,S} &\rightarrow \min(dp_{l,r,S}, dp_{l+1,r,S}, dp_{l,r-1,S}), \\ dp_{l,r,S} &\rightarrow \min(dp_{l,r,S}, \min_{T \in S} dp_{l,l+len_T-1,T} + dp_{l+len_T,r,S}\cap c_S T), \end{aligned}$$

表示把 $S$ 这个集合的答案拆成两部分计算。

$$\begin{aligned} dp_{l,r,S} &\rightarrow \min(dp_{l,r,S}, \min_{t \in S} dp_{l+1,r-1,\{x \mid x \in S,x=t\}} + |L - b_l| + (r-l) + |b_r - R|), \end{aligned}$$

表示选择 $(l, r)$ 作为编号为 $t$ 的段对应的数对。